package leetcode.code0971;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import leetcode.IDebug;
import leetcode.helper.tree.TreeNode;

public class Solution implements IDebug {

	List<Integer> ans;

	public List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {
		ans = new ArrayList<>();
		boolean ok = this.find(root, voyage, 0, voyage.length - 1);
		return ok ? ans : Arrays.asList(new Integer[] { -1 });
	}

	private boolean find(TreeNode root, int[] voyage, int L, int R) {
		if (root == null) {
			return L > R;
		}
		if (L > R && root != null) {
			return false;
		}
		int cur = root.val;
		if (cur != voyage[L]) {
			return false;
		}
		if (root.left == null && root.right == null) {
			if (L != R || cur != voyage[L]) {
				return false;
			}
			return true;
		}
		if (root.left == null) {
			return this.find(root.right, voyage, L + 1, R);
		} else if (root.right == null) {
			return this.find(root.left, voyage, L + 1, R);
		}
		if (R - L < 2) {
			return false;
		}
		int left = root.left.val, li = -1;
		int right = root.right.val, ri = -1;
		for (int i = L + 1; i <= R; i++) {
			int num = voyage[i];
			if (num == left) {
				li = i;
			} else if (num == right) {
				ri = i;
			}
		}
		if (li != L + 1 && ri != L + 1) {
			return false;
		}
		if (li == -1 || ri == -1) {
			return false;
		}
		if (li < ri) {
			boolean ans1 = this.find(root.left, voyage, li, ri - 1);
			boolean ans2 = this.find(root.right, voyage, ri, R);
			return ans1 && ans2;
		}
		ans.add(cur);
		boolean ans1 = this.find(root.right, voyage, ri, li - 1);
		boolean ans2 = this.find(root.left, voyage, li, R);
		return ans1 && ans2;
	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
